﻿// 0824train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <map>
#include <set>

using namespace std;

/*
 跳房子，也叫跳飞机，是一种世界性的儿童游戏。 
游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格 
跳房子的过程中，可以向前跳，也可以向后跳。 
假设房子的总格数是count，小红每回合可能连续跳的步教都放在数组steps中，
请问数组中是否有一种步数的组合，可以让小红两个回合跳到最后一格? 
如果有，请输出索引和最小的步数组合。 

注意: 
- 数组中的步数可以重复，但数组中的元素不能重复使用。 
- 提供的数据保证存在满足题目要求的组合，且索引和最小的步数组合是唯一的

输入描述
第一行输入为每回合可能连续跳的步数，它是整数数组类型。
第二行输入为房子总格数count，它是int整数类型。
count ≤ 1000
0 ≤ steps.length ≤ 5000
-100000000 ≤ steps ≤ 100000000

输出描述
返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序)

输入
[1,4,5,2]
7
输出
[5,2]
两个回合跳到最后一格，两数之和
索引和最小
 */
void solve01(vector<int>&num_vec, int target)
{
	int index_sum = INT_MAX;
	vector<int>result;
	unordered_map<int,int>index_map;
	for (int i=0; i<num_vec.size(); i++)
	{
		int curr_num = num_vec[i];
		
		if (index_map.count(curr_num)>0)
		{
			int prev_index = index_map.at(curr_num);
			if (prev_index+i<index_sum)
			{
				index_sum = prev_index + i;
				int prev_num = num_vec[prev_index];
				result.clear();
				result.push_back(prev_num);
				result.push_back(curr_num);
			}
		}
		else
		{
			index_map[target - curr_num] = i;
		}

	}

	if (!result.empty())
	{
		cout << '[' << result[0] << ',' << result[1] << ']';
	}
	//solve01---
}


/*
 部门在进行需求开发时需要进行人力安排。
 当前部门需要完成 N 个需求，需求用 requirements[i] 表示，
 requirements[i] 表示第 i 个需求的工作量大小，单位：人月。
 这部分需求需要在 M 个月内完成开发，进行人力安排后每个月的人力是固定的。 

目前要求每个月最多有 2 个需求开发，并且每个月需要完成的需求不能超过部门人力。
请帮部门评估在满足需求开发进度的情况下，每个月需要的最小人力是多少

输入描述
输入第一行为 M ，第二行为 requirements 。 
M 表示需要开发时间要求，requirements 表示每个需求工作量大小 N 为 requirements 长度，
1 ≤ N / 2 ≤ M ≤ N ≤ 10000，1 ≤ requirements[i]≤ 10^9

输出描述
对于每一组测试数据，输出部门需要人力需求，行末无多余的空格。

输入
3
3 5 3 4
输出
6

输入
3个月内完成，3 5 3 4工作量大小，最多2个需求开发
3 5 3 4
输出
6
输入数据两行，
第一行输入数据 3 表示开发时间要求，
第二行输入数据表示需求工作量大小，输出数据一行，表示部门人力需求。
当选择人力为6时，2个需求量为3的工作可以在1个月里完成，其他2个工作各需要1个月完成。可以在3个月内完成所有需求。
当选择人力为5时，4个工作各需要1个月完成，一共需要4个月才能完成所有需求。
因此6是部门最小的人力需求
 */

class Solution02
{
public:
	int computedTime(vector<int>&num_vec,int limit)
	{
		int left = 0, right = num_vec.size() - 1;
		int result = 0;
		while (left<=right)
		{
			if (left==right)
			{
				result += 1;
				break;
			}
			if (num_vec[left]+num_vec[right]<=limit)
			{
				result += 1;
				left++;
				right--;
			}
			else
			{
				result += 1;
				right--;
			}

		}
		return result;
	}

	void solve02(vector<int>&num_vec, int time_limit)
	{
		sort(num_vec.begin(), num_vec.end());

		int vec_size = num_vec.size();
		//每个月需要完成的需求不能超过部门人力
		int left = num_vec[vec_size - 1], right = 2 * num_vec[vec_size - 1];

		int result = INT_MAX;
		while (left<right)
		{
			int mid = left + (right - left) / 2;
			if (computedTime(num_vec, mid)<=time_limit)
			{
				result = min(result, mid);
				//调小人力
				right = mid;
			}
			else
			{
				//调大人力
				left = mid + 1;
			}
		}

		cout << result;
		//solve02
	}

};


/*
 有N (3 <= N < 10000)个运动员，他们的id为0到N-1,他们的实力由一组整数表示。
 他们之间进行比赛，需要决出冠亚军。比赛的规则是0号和1号比赛，2号和3号比赛，
 以此类推，每一轮，相邻的运动员进行比赛，获胜的进入下一轮，实力值大的获胜，
 实力值相等的情况，id小的情况下获胜；轮空的直接进入下一轮。

输入描述
输入一行N个数字代表N个运动员的实力值(0 <= 实力值 <= 10000000000).

输出描述
输出冠亚季军的id，用空格隔开

输入
2 3 4 5
输出
3 1 2
 */
class Solution03
{
public:
	void solve03(vector<pair<int,int>>&num_vec)
	{
		//val index
		while (num_vec.size()>=5)
		{
			vector<pair<int, int>>new_vec;
			for (int i=0; i<num_vec.size();i+=2)
			{
				pair<int, int>first_pair = num_vec[i];
				pair<int, int>second_pair = num_vec[i + 1];

				if (first_pair.first>=second_pair.first)
				{
					new_vec.push_back(first_pair);
				}
				else
				{
					new_vec.push_back(second_pair);
				}

			}

			//奇数，最后一个轮空
			if (num_vec.size()%2!=0)
			{
				pair<int, int>last_pair = num_vec[num_vec.size() - 1];
				new_vec.push_back(last_pair);

			}
			num_vec = new_vec;
		}

		//for (auto&pair_item:num_vec)
		//{
		//	cout << pair_item.first << endl;
		//}
		vector<int>result_vec(3);
		if (num_vec.size()==3)
		{
			pair<int, int>A, B, C;
			A = num_vec[0];
			B = num_vec[1];
			C = num_vec[2];

			if (A.first>B.first)
			{
				result_vec[0] = A.second;
				result_vec[1] = B.second;
			}

		}

		if (num_vec.size()==4)
		{
			
		}

		//solve03------
	}
	
};

int main()
{
	{
		string input = "2 3 4 5 6 7";
		stringstream oh_sstream(input);
		string token;
		vector<pair<int,int>>num_vec;
		int index = 0;
		while (oh_sstream>>token)
		{
			pair<int, int>curr = make_pair(stoi(token), index);
			num_vec.push_back(curr);
			index++;
		}

		Solution03 solu;
		solu.solve03(num_vec);

		return 0;
	}
	{
		//3
		//3 5 3 4
		//int limit = 3;
		//vector<int>num_vec = { 3,5,3,4 };
		int limit;
		cin >> limit;
		cin.ignore();

		vector<int>num_vec;
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		while (oh_sstream>>token)
		{
			num_vec.push_back(stoi(token));
		}

		Solution02 solu;
		solu.solve02(num_vec, limit);

		return 0;
	}
	//[3,4,5,2] 7
	//string num_str = "[-1,2,4,9,6]";
	//int target = 8;
	string num_str;
	int target;
	cin >> num_str;
	cin >> target;
	num_str.erase(0, 1);
	num_str.erase(num_str.size() - 1, 1);

	vector<int>num_vec;
	stringstream oh_sstream(num_str);
	string token;
	while (getline(oh_sstream,token,','))
	{
		num_vec.push_back(stoi(token));
	}

	solve01(num_vec, target);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
